package tianhao.luo.algorithm;

/**
 * 快速排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  16:12
 */
public class QuickSort {

    private int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public void sort(int left, int right) {
        // 先找到中间的值
        int pivot = array[(left + right) / 2];

        // 左下标
        int l = left;
        // 有下标
        int r = right;

        int temp;
        // while循环的目的是让比pivot值小的放到左边
        // 比pivot大的放到右边
        // 因为l是从数组左边开始向右扫描,r是从数组右边开始向左扫描;所以要求l<r
        while (l < r) {

            // 在pivot左边,一直找,找到一个大于等于pivot的值才退出
            // 肯定能找到一个等于pivot的array[l],不用管会陷入死循环
            // 如果一直没找到array[l]>pivot,则l就会等于pivot的索引
            while (array[l] < pivot) {
                l++;
            }
            // 在pivot右边,一直找,找到一个小于等于pivot的值就退出
            while (array[r] > pivot) {
                r--;
            }

            // 如果l==r,说明pivot的左右两边的值,已经按照左边全部小于pivot,右边全部大于pivot的排列了
            if (l ==r){
                break;
            }

            // 否则就交换
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;


            // 存在和pivot值相同的元素时,如果交换完成后,发现array[l]==pivot时,表示上面交换前的索引为r的元素值等于pivot,
            // 这次交换我们认为是有效的,需要让r--,即向前移动一步;否则再次进入循环时,因为r没有变化,就不会进入
            // while (array[r] > pivot循环内部,就会始终执行交换操作,出现死循环
            if (array[l]==pivot){
                r--;
            }
            // 如果交换完成后,发现array[r]==pivot时,需要让l++,即向后移动一步
            if (array[r]==pivot){
                l++;
            }
        }

        // 如果l == r,必须l++,r--,否则出现栈溢出
        // 因为后续对pivot左半部分和右半部分进行排序时,可能会递归产生堆栈溢出

        // 我们以左半部分为例,假设左半部分是有序的且只有三个元素,经历了上面的while循环后,l和r最终都是1
        // 那么left为0,会始终满足left<r,递归产生堆栈溢出;同理右半部分也是如此.
        if (l == r){
            l++;
            r--;
        }
        // 向左递归
        if (left<r){
            sort(left,r);
        }
        // 向右递归
        if (right>l){
            sort(l,right);
        }
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
